//package com.lwl.mycode.mycode.class20暴力递归2动态规划;
//
//import com.lwl.Utils.Utils.PrintUtil;
//import mycode.algorithmbasic.class20.Code01_PalindromeSubsequence;
//
///**
// * @author lwl
// * @Description 最长回文子序列
// * str : 1234321
// * ans : 1234321
// * 可以取巧：上一道求两个字符串的最长公共子序列，这里把原字符串倒序，将倒序字符串和原字符串求最长公共子序列即可
// * @date 2023/6/7 21:02
// */
//public class Code01LongestPalindromeSubsequence {
//
//    public static void main(String[] args) {
//        String str = "1sbsdbfjlwqieoushadbvcxnvasdcxvqwsa";
//        //                String str = "1234321";
//        //        System.out.println(longestPalindromeSubsequence(str));
//        System.out.println(Code01_PalindromeSubsequence.longestPalindromeSubseq2(str));
//        System.out.println(longestPalindromeSubsequence1(str));
//    }
//
//    static private int longestPalindromeSubsequence1(String str) {
//        int n = str.length();
//        int[][] dp = new int[n][n];
//        for (int i = 0; i < n; i++) {
//            dp[i][i] = 1;
//        }
//        // 类似 {@link Code02CardInLine}
//        // 左上到右下的对角线，然后这条对角线往右上移动的
//        for (int i = 1; i < n; i++) {
//            int left = 0;
//            int right = i;
//            while (right < n) {
//                int p1 = dp[left + 1][right];
//                int p2 = dp[left][right - 1];
//                int p3 = dp[left + 1][right - 1];
//                if (str.charAt(left) == str.charAt(right)) {
//                    p3 = dp[left + 1][right - 1] + 2;
//                }
//                dp[left][right] = Math.max(Math.max(p1, p2), p3);
//                left++;
//                right++;
//            }
//        }
//        PrintUtil.printArray(dp);
//        return dp[0][n - 1];
//    }
//
//    static private int longestPalindromeSubsequence(String str) {
//        return process(str, 0, str.length() - 1);
//    }
//
//    /**
//     * 求字符串str在【left，right】之间的最长回文子序列
//     */
//    private static int process(String str, int left, int right) {
//        if (left > right) {
//            return 0;
//        }
//        if (left == right) {
//            return 1;
//        }
//        int p1 = process(str, left + 1, right);
//        int p2 = process(str, left, right - 1);
//        int p3 = 0;
//        if (str.charAt(left) == str.charAt(right)) {
//            p3 = process(str, left + 1, right - 1) + 2;
//        }
//        return Math.max(Math.max(p1, p2), p3);
//    }
//
//}
